#include "thread.h"

extern func_BiTree fBiTree;

/**
 *  功 能：
 *      线索化二叉树 -- 先序线索化
 *  参 数：
 *      root：要线索化的树的根节点
 *      ptmp：用于保留前驱节点
 *  返回值：
 *      无
 **/
void prev_thread(BiTNode *root, BiTNode **ptmp)
{
    if ((root == NULL))
        goto END;

    if (root->lchild == NULL)
    {
        root->lchild = *ptmp;
        root->lTag = 1;
    }
    if (*ptmp != NULL && (*ptmp)->rchild == NULL)
    {
        (*ptmp)->rchild = root;
        (*ptmp)->rTag = 1;
    }

    (*ptmp) = root;

    //如果不判断就会造成死循环，造成栈溢出
    if (root->lTag == 0)
        prev_thread(root->lchild, ptmp);
    //同理，因为在程序一开始就对其左右孩子为NULL时就做了前驱后继的处理，但是改了标志位，所以此处可根据标志位判断是子树还是前驱后继
    if (root->rTag == 0)
        prev_thread(root->rchild, ptmp);
END:
    return;
}

/**
 *  功 能：
 *      先序线索化二叉树的前驱节点
 *  参 数：
 *      root：要查找的节点
 *  返回值：
 *      成功：节点的后继节点
 *      失败：NULL
 **/
BiTNode *prev_thread_prevNode(BiTNode *root)
{
    BiTNode *ret = NULL;

    if (root == NULL)
        goto END;
END:
    return ret;
}

/**
 *  功 能：
 *      先序线索化二叉树的后继节点
 *  参 数：
 *      root：要查找的节点
 *  返回值：
 *      成功：节点的后继节点
 *      失败：NULL
 **/
BiTNode *prev_thread_nextNode(BiTNode *root)
{
    BiTNode *ret = NULL;

    if (root == NULL)
        goto END;

    if (root->lTag == 0) // 左标志位 0，是为其左孩子，也就是后继节点
    {
        ret = root->lchild;
    }
    else // 如果rTag为1，是为正确后继，如果rTag为0，为右孩子
    {
        ret = root->rchild;
    }

END:
    return ret;
}

/**
 *  功 能：
 *      遍历线索化二叉树 - 使用先序的后继节点
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void prev_thread_Older_byNextNode(BiTNode *root)
{
    if (root == NULL)
        goto END;

    while (root)
    {
        printf("%c ", root->data);
        root = prev_thread_nextNode(root);
    }

END:
    printf("\n");
    return;
}
/**
 *  功 能：
 *      遍历线索化二叉树 - 使用先序的前驱节点
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void prev_thread_Older_byPrevNode(BiTNode *root)
{
    if (root == NULL)
        goto END;

END:
    return;
}
/**
 *  功 能：
 *      遍历线索化二叉树 - 使用先序线索化的标识
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void prev_thread_Older_normal(BiTNode *root)
{
    if (root == NULL)
        goto END;

    BiTNode *p = root;
    while (p != NULL)
    {
        while (p->lTag == 0)
        {
            printf("%c ", p->data);
            p = p->lchild;
        }
        printf("%c ", p->data);
        p = p->rchild;
    }

END:
    printf("\n");
    return;
}

funThread fthread = {
    prev_thread,

    prev_thread_Older_byNextNode,
    prev_thread_Older_byPrevNode,
    prev_thread_Older_normal,

    prev_thread_nextNode,
    prev_thread_prevNode

};
